package com.arron.algorithm.leetcodetop100.回溯.排列and组合and子集;

import java.util.ArrayList;
import java.util.List;

public class 组合总和III {


    List<List<Integer>> combinationList;
    int sum;
    public List<List<Integer>> combinationSum3(int k, int n) {

        combinationList = new ArrayList<>();
        List<Integer> path =  new ArrayList<>();

        combinationSum3(k,path,n,1);
        return combinationList;
    }

    public void combinationSum3(int k, List<Integer> path,int target,int start){

        if (path.size() == k && sum == target){
            combinationList.add(new ArrayList<>(path));
            return;
        }
        if (sum>target || path.size() >k){
            return;
        }
        for (int i = start; i <=9 ; i++) {
            sum+=i;
            path.add(i);
            combinationSum3(k,path,target,i+1);
            sum-=i;
            path.remove(path.size()-1);
        }

    }

}
